As is known in the art, a network includes a set of processing sites generally referred to as stations or nodes connected by one or more physical and/or logical connections generally referred to as links, which may be uni-directional or bi-directional in nature. Each node typically performs a switching function and one or more additional functions.
The nodes may be coupled together in a variety of different network structures typically referred to as network topologies. For example, network nodes made be coupled in a circular structure, referred to as a ring topology. Other topologies such as star topologies and mesh topologies are also known.
The transmission of a signal from a first or source node to a second or destination node may involve the transmission of the signal through a plurality of intermediate links and nodes coupled between the source node and the destination node. Such a succession of links and nodes between a source node and a destination node is referred to as a path.
When a link or node in a path fails, communication between a source node and a destination node in that path is disrupted. Thus, to continue communications between the source and destination nodes, another path must be found and the signal being transmitted from the source node to the destination is routed through the new path. This path determination can be a complex time intensive operation resulting in a long delay before the disrupted communications are fixed. The magnitude of this process increases greatly with network topology size.
One approach to providing failure tolerance in such networks is to identify during initial service configuration a primary path through the network and one or more non-primary paths or protection paths through the network simultaneously, so-called “multi-path routing”. For example, methods are available of identifying two paths such that they are maximally edge disjoint, meaning that the two paths share as few links as possible—usually no links, and methods are available of identifying two paths such that they are maximally node disjoint, meaning that the two paths share as few nodes as possible—usually no nodes. Once a failure (link or node) occurs, the signals are automatically switched or protection switched on these protection path(s) drastically reducing disruption time. Thus, ensuring edge/node resource disjointness is important.
Some links and/or nodes in a network may share common risk of failure. For example, there may be multiple links which at some point share a common resource such as a common single cable. Such links would simultaneously fail in the event of the failure of the common resource. Groups of network resources which share common risks are referred to herein as “shared risk groups” or SRGs. Existing route definition methods such as the above-noted maximally disjoint approaches do not address the issue of shared risk groups, resulting in the possibility that the primary and non-primary paths will share some resources even though they do not share any links and/or nodes.